Представляем план лекции. Перечислим основные темы: от определения тупика до практических примеров обработки в реальных системах.
Начинаем с базового определения тупика. Подчеркните: это не замедление, а полная permanent блокировка группы процессов.
Классический пример с двумя процессами и двумя ресурсами. Покажите пошагово, как возникает взаимная блокировка.
Переходим к условиям Кофмана — теоретической основе анализа тупиков. Все четыре условия должны выполняться одновременно, иначе тупик невозможен.
Первое условие. Приведите примеры: принтер, мьютекс, файл на запись — ресурсы, которые не могут быть разделяемыми.
Второе условие — процесс «держит своё и просит чужое». Это ключевой паттерн, ведущий к тупику.
Третье условие. Сравните вытесняемые ресурсы (CPU, память) и невызываемые (принтер, БД-блокировка).
Четвёртое условие замыкает круг: процессы образуют кольцо ожидания. Покажите математическую запись цикла.
Граф ресурсов — наглядный инструмент моделирования тупиков. Обратите внимание на обозначения: круги — процессы, квадраты — ресурсы.
Разбираем конкретный пример графа. Цикл в графе однозначно указывает на тупик при одном экземпляре каждого ресурса.
Четыре стратегии обработки тупиков: от простого игнорирования до обнаружения и восстановления. Каждая имеет свои компромиссы.
Начинаем блок предотвращения. Первая стратегия — сделать ресурсы совместно используемыми. Spooling для принтера — классический пример обхода взаимного исключения.
Вторая стратегия: заставить процесс запрашивать все ресурсы сразу. Простая идея, но ведёт к неэффективному использованию ресурсов и возможному голоданию.
Третья стратегия: разрешить ОС принудительно изымать ресурсы. Работает для CPU и памяти, но не для принтера в середине печати.
Четвёртая стратегия — нумерация ресурсов и строгий порядок запросов. Гарантированно устраняет циклы, используется в некоторых ядрах ОС.
Ключевое понятие для избегания тупиков. Безопасное состояние означает, что система гарантированно может завершить все процессы без тупика.
Алгоритм банкира — классический метод Дейкстры для избегания тупиков. Объясните аналогию с банком, выдающим кредиты.
Пошаговый алгоритм проверки безопасности. Ищем процесс, который может завершиться, и моделируем освобождение его ресурсов.
Как система обрабатывает запрос ресурса от процесса. Пробное распределение + проверка безопасности — двухфазный подход.
Когда алгоритм банкира слишком дорог по накладным расходам — используем обнаружение. Обсудите, в каких случаях это оправдано.
Для одного экземпляра ресурса используем граф ожидания. Поиск цикла через DFS — простая и эффективная проверка за O(n²).
Обобщение на несколько экземпляров ресурса. Алгоритм аналогичен проверке безопасности, но использует текущие запросы процессов.
Обнаружили тупик — что делать? Простейший способ — прервать процесс. Обсудите критерии выбора «жертвы»: приоритет, время, ресурсы.
Более тонкие методы восстановления: откат к контрольной точке и принудительное изъятие ресурсов. У каждого метода есть ограничения.
На практике применяют комбинации стратегий. Иерархия ресурсов позволяет выбрать оптимальный метод для каждого класса.
Реальные примеры из UNIX/Linux и Windows. Обе ОС используют комбинации стратегий, но с разными акцентами и приоритетами.
СУБД — классическая область, где тупики возникают часто. Транзакции и ACID-свойство Atomicity позволяют безопасно откатывать изменения.
Переходим к заключительной части. Подведём итоги лекции и сформулируем ключевые выводы.
Главный вывод: нет универсального решения. Выбор стратегии зависит от требований системы и характера ресурсов. На практике чаще всего — игнорирование и перезагрузка.
Вопросы для самопроверки покрывают все ключевые темы. Рекомендуйте студентам использовать их для подготовки к экзамену.
Основной учебник — Таненбаум. Silberschatz рекомендуется для углублённого изучения темы тупиков и распределённых систем.